# -*- encoding: utf-8 -*-


def heapify(unsort, index, heap_size):
    """堆化函数：将list中数据转换成符合完全二叉树的堆结构"""
    m = index
    left_index = index * 2 + 1 if index * 2 + 1 < heap_size else None
    right_index = index * 2 + 2 if index * 2 + 2 < heap_size else None

    if left_index and unsort[left_index] > unsort[m]:
        m = left_index
    if right_index and unsort[right_index] > unsort[m]:
        m = right_index
    if m != index:
        unsort[index], unsort[m] = unsort[m], unsort[index]
        heapify(unsort, m, heap_size)


def heap_sort(unsort):
    """将堆结构数据进行排序"""
    n = len(unsort)
    for i in range(n // 2 - 1, -1, -1):
        heapify(unsort, i, n)
    for i in range(n - 1, 0, -1):
        unsort[0], unsort[i] = unsort[i], unsort[0]
        heapify(unsort, 0, i)
    return unsort


if __name__ == '__main__':
    print(heap_sort(unsort=[20, 19, 16, 7, 8, 13, 5, 4, 1, 9]))
